Motion estimation is the most computationally expensive element in a video compression system. In typical video encoding systems, motion estimation uses up to 80% of the computational resources. Motion estimation is performed through a process called block-matching. Block-matching involves comparing a block of pixels in an original picture (for which motion is being estimated) to blocks of pixels at many positions in a reference picture. At each position, a block-matching cost function is evaluated to assess the quality of the block-match. The position that results in the lowest value of the cost function is taken to be the optimal position for motion compensated coding for the original block of pixels.
A solution that reduces the total computation required for motion estimation would be desirable.